#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 链式栈定义（带头结点）
typedef struct SNode
{
    int data;
    struct SNode *next;
} SNode, *Stack;

// 初始化：创建头结点
void InitStack(Stack &S)
{
    S = (SNode *)malloc(sizeof(SNode));
    if (S == NULL)
    {
        printf("内存分配失败！\n");
        exit(-1);
    }
    S->next = NULL;
}

// 判空（栈是否只有头结点）
bool IsEmpty(Stack &S)
{
    if (S->next == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

// 入栈（头插法）
void Push(Stack &S, int x)
{
    SNode *newNode = (SNode *)malloc(sizeof(SNode));
    if (newNode == NULL)
    {
        printf("内存分配失败！\n");
        exit(-1);
    }
    newNode->data = x;
    newNode->next = S->next;
    S->next = newNode;
}

// 出栈
bool Pop(Stack &S, int &x)
{
    if (IsEmpty(S))
        return false;

    SNode *temp = S->next;
    x = temp->data;
    S->next = temp->next;
    free(temp);
    return true;
}

// 查看栈顶元素但不删除
bool GetTop(Stack &S, int &x)
{
    if (IsEmpty(S))
        return false;

    x = S->next->data;
    return true;
}

// 打印栈内容（从栈顶到底部）
void PrintStack(Stack &S)
{
    printf("栈内容：");
    SNode *p = S->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 清空栈（保留头节点）
void ClearStack(Stack &S)
{
    int temp;
    while (!IsEmpty(S))
    {
        Pop(S, temp);
    }
}

// 销毁整个栈（包括头节点）
void DestroyStack(Stack &S)
{
    ClearStack(S);
    free(S);
    S = NULL;
}

// 测试
int main()
{
    Stack s;
    InitStack(s);

    Push(s, 10);
    Push(s, 20);
    Push(s, 30);

    PrintStack(s); // 应该打印：30 20 10

    int top;
    if (GetTop(s, top))
    {
        printf("当前栈顶元素：%d\n", top);
    }

    int popped;
    if (Pop(s, popped))
    {
        printf("弹出元素：%d\n", popped);
    }

    PrintStack(s); // 应该打印：20 10

    ClearStack(s);
    printf("栈是否为空：%s\n", IsEmpty(s) ? "是" : "否");

    DestroyStack(s); // 彻底释放所有内存
    return 0;
}
